from typing import List


class Solution:
    def pileBox(self, box: List[List[int]]) -> int:
        # 依据长宽高总和排序箱子
        # O(NlogN)
        box.sort(key=lambda x: sum(x), reverse=True)

        # 初始化状态表格
        dp = [b[2] for b in box]

        # 状态转移
        # max_idx, max_val = 0, dp[0]
        for i in range(1, len(box)):
            w1, d1, h1 = box[i]
            max_height = 0
            for j in range(i - 1, - 1, -1):
                w2, d2, h2 = box[j]
                if w1 < w2 and d1 < d2 and h1 < h2:
                    max_height = max(max_height, dp[j])

            dp[i] = max(dp[i], max_height + h1)
            # if dp[i] > max_val:
            #     max_idx, max_val = i, dp[i]

        return max(dp)


if __name__ == "__main__":
    # 6
    print(Solution().pileBox(box=[[1, 1, 1], [2, 2, 2], [3, 3, 3]]))

    # 10
    print(Solution().pileBox(box=[[1, 1, 1], [2, 3, 4], [2, 6, 7], [3, 4, 5]]))

    # 27
    print(Solution().pileBox(
        box=[[9, 9, 10], [8, 10, 9], [9, 8, 10], [9, 8, 10], [10, 8, 8], [9, 8, 9], [9, 8, 8], [8, 9, 10], [10, 9, 10],
             [8, 8, 10], [10, 9, 10], [10, 9, 8], [8, 9, 9], [9, 10, 8], [8, 9, 9], [10, 10, 9], [8, 9, 10],
             [8, 10, 10], [8, 9, 10], [10, 10, 8], [10, 10, 9], [9, 10, 10], [10, 8, 9], [10, 10, 9], [8, 9, 10],
             [8, 8, 9], [8, 10, 10], [9, 9, 10], [10, 8, 8], [10, 10, 8], [8, 9, 9], [8, 9, 8], [10, 10, 8], [8, 10, 8],
             [10, 9, 10], [9, 9, 10], [9, 9, 9], [8, 9, 8], [9, 8, 8], [8, 9, 10], [10, 10, 8], [9, 9, 9], [10, 10, 10],
             [10, 9, 8], [9, 8, 9], [8, 8, 10], [8, 8, 8], [8, 8, 8], [8, 9, 10], [10, 9, 8], [8, 10, 8], [8, 10, 10],
             [9, 10, 10], [8, 8, 9], [9, 9, 9], [10, 8, 8], [8, 10, 10], [9, 10, 9], [9, 9, 8], [8, 10, 9], [9, 8, 8],
             [9, 9, 10], [9, 10, 10], [8, 8, 10]]))

    # 70
    print(Solution().pileBox(
        [[3, 1, 4], [10, 16, 15], [9, 10, 20], [8, 9, 8], [19, 7, 8], [10, 8, 2], [18, 16, 6], [8, 4, 9], [13, 1, 10],
         [18, 4, 6], [14, 8, 16], [13, 18, 2], [17, 10, 16], [4, 6, 6], [11, 17, 7], [1, 8, 7], [16, 10, 15],
         [18, 18, 4], [7, 2, 12], [1, 7, 3], [8, 5, 4], [15, 4, 9], [16, 7, 6], [12, 13, 20], [2, 4, 3], [12, 13, 20],
         [1, 2, 13], [16, 20, 11], [14, 4, 17], [16, 15, 8], [15, 18, 17], [4, 4, 8], [5, 18, 1], [16, 10, 10],
         [17, 19, 13], [18, 20, 13], [17, 5, 19], [5, 2, 17], [7, 13, 13], [9, 11, 12], [11, 10, 12], [10, 16, 5],
         [4, 3, 18], [18, 11, 18], [14, 14, 16], [18, 1, 14], [7, 5, 19], [10, 15, 11], [2, 11, 8], [6, 8, 17],
         [12, 1, 12], [8, 4, 17], [13, 14, 11], [17, 20, 11], [15, 10, 15], [7, 6, 19], [14, 13, 15], [11, 9, 12],
         [19, 14, 2], [14, 11, 8], [4, 2, 18], [12, 20, 15], [2, 12, 18], [16, 6, 9]]))
